1. Field
The following description relates to a digital information processing, and more particularly, to a call graph construction method.
2. Description of the Related Art
Dynamic call graph is abstraction used for representing execution paths of a program or an application. That is, dynamic call graph of functions is used to profile computer programs or applications. This information may be used to understand a behavior of the application and detect errors, and to perform an analysis of the application.
To obtain an accurate dynamic call graph, a method of tracing of all function calls in an application may be used. This method uses instrumentation of all functions of the application. Instrumentation may assume changes in a function code for information collection capability. During the tracing method, information about all executed functions is saved in the trace. However, this method may require a large amount of memory (or storage space), and slow down the application due to the overhead from collecting the information. Thus, obtaining an accurate dynamic call graph may be problematic with embedded systems with limited resources, especially for larger applications.
Alternatively, a method of sampling call stack may be used to construct a dynamic call graph. The sampling call stack method calls for periodic saving of call stack information. However, this method may suffer from low precision because some of the call stack information may be lost.
U.S. Pat. No. 6,662,358 describes a combined method of tracing and sampling to decrease the overhead from tracing and increase the precision of sampling. This method generates a trace record containing a call stack associated with a program periodically. Also, the trace record contains information of context of execution. During a post-processing, the information of context of execution is compared with samples of the call stack to identify the routine associated with the program, that is, a routine associated with execution of sample data or path of execution of the program. Still, this method may have low precision and involve a lot of hardware resources.
U.S. Pat. No. 6,002,872 describes a method of sampling a call stack. In the method, a periodically occurring event is detected, a call stack associated with a program is identified in response to the detection of the periodically occurring event. Dynamic call graph is created during a post-processing stage by using call stack samples. Drawbacks of this method may still include involving a lot of hardware resources and low precision.
U.S. Pat. No. 6,751,789 describes a method for tracing function calls where trace collection is periodically paused to decrease the overhead. This method may still involve a lot of hardware resources and have low precision.
U.S. Pat. No. 6,049,666 describes a software profiling method where tracing of all functions are executed. This method may involve a lot of hardware resources, and accordingly, may not be applied to a built-in system environment with limited resources.